# 希尔排序练习
# 2022-5-17
from utils.array_utils import check_all


def shell(l):
    gap = len(l)
    gap //= 5
    count = 0
    while gap > 0:
        i = gap
        while i < len(l):
            cur = l[i]
            pre = i - gap
            while pre >= 0 and cur < l[pre]:
                count += 1
                # print(cur, l[pre])
                l[pre + gap] = l[pre]
                pre -= gap
            l[pre + gap] = cur

            # print(l[i])
            i += gap
        gap //= 2
        # print(gap, '---')
    return count


def shell_02(l):
    """ 再次练习希尔排序 """
    count = 0
    gap = len(l) // 2
    while gap > 0:
        # print(gap)
        # for循环起始值为0与gap效果是一样的
        for i in range(gap, len(l), gap):
            # print(l[i])
            cur = l[i]
            pre = i - gap
            while pre >= 0 and cur < l[pre]:
                count += 1
                l[pre + gap] = l[pre]
                pre -= gap
            l[pre + gap] = cur
        gap //= 2
        # print('--')
    return count


if __name__ == '__main__':
    l = [49, 10, 96, 78, 57, 33, 66, 21, 49, 10, 96, 78, 57, 33, 66, 21, 87, -5, 91, 2, -51, 22, -18, -84, 49, 56]
    # l = [49, 10, 96, 78, 57, 33, 66, 21, 49, 10, 96]
    print(shell_02(l))
    print(l)
    check_all(shell_02, 1000)
